import { AbEqualToOther, Derivation, EqualToEqualToOther, Grammar, GrammarToken } from "./common_lr";
import { ContainerMarkableBox } from "./ContainerMarkableBox";


///////////////////////////////// LR(0) /////////////////////////////////

/**
 * 项目集规范族 LR(0) - 项目
 * 
 * A -> • B a    pos = 0
 * A ->  B • a    pos = 1
 * A ->  B a •    pos = 2
 */
export class FamilyItemsLR0 implements AbEqualToOther {
    readonly dervation: Derivation;
    readonly pos: number;
    constructor(d: Derivation, pos: number) {
        this.dervation = d;
        this.pos = pos;
    }
    equalToOther(other: FamilyItemsLR0): boolean {
        return this.dervation === other.dervation && this.pos === other.pos;
    }

    // equalToOther<T>(other: FamilyItemsLR0): boolean {
    //     if (other === this) {
    //         return true;
    //     }

    //     return this.dervation === other.dervation && this.pos === this.pos;
    // }


    /**
     * 是规约项目？
     */
    isReduce() {
        return this.pos === this.dervation.right.length;
    }

    /**
     * 是移入项目？
     */
    isShift() {
        return this.pos < this.dervation.right.length;
    }

    get facedToken(): GrammarToken | null {
        return this.isShift() ? this.dervation.right[this.pos] : null;
    }
    
    /**
     *  A ->  B • a C D 则 返回  a C D
     */
    genFacedTokenList(): GrammarToken[] {
        return this.dervation.right.slice(this.pos, this.dervation.right.length);
    }
    

    static equal(a: FamilyItemsLR0, b: FamilyItemsLR0) {
        return EqualToEqualToOther(a, b);
    }

    toString(): string {
        const rightList: any = [...this.dervation.right];
        rightList.splice(this.pos, 0, "•");
        return `${this.dervation.left} -> ${rightList.join(" ")}`
    }
}


/**
 * 项目集规范族 LR(0) - 集合
 */
export class FamilyItemsSetLR0 implements AbEqualToOther {
    readonly container: FamilyItemsLR0[] = [];

    /**
     * 去重添加，如果重复则不添加
     * @param item 
     * @returns 成功添加返回真，否则，返回假
     */
    addItem(item: FamilyItemsLR0): boolean {
        for (const oi of this.container) {
            if (oi.equalToOther(item)) {
                return false;
            }
        }

        this.container.push(item);
        return true;
    }

    /**
     * 比较相等， 可以通过 Hash 优化
     * @TODO Hash 优化
     */
    equalToOther(other: FamilyItemsSetLR0): boolean {
        if (this === other) {
            return true;
        }

        if (other.container.length != this.container.length) {
            return false;
        }

        for (let idx = 0; idx < this.container.length; idx++) {
            const left = this.container[idx];
            const right = other.container[idx];
            if (!left.equalToOther(right)) {
                return false;
            }
        }
        return true;
    }

    static equal(a: FamilyItemsSetLR0, b: FamilyItemsSetLR0) {
        return EqualToEqualToOther(a, b);
    }

    toString(): string {
        return this.container.join("\n");
    }
}

/**
 * 项目集规范族 LR(0)
 */
export class FamilyItemsTableLR0 {
    private g: Grammar;
    constructor(g: Grammar) {
        this.g = g;
    }

    private ExtendSetFrom(srcList: FamilyItemsLR0[]): FamilyItemsSetLR0 {
        const box = new FamilyItemsSetLR0();
        const queue: FamilyItemsLR0[] = [];
        this.cachedDerivationMap = this.cachedDerivationMap ?? this.g.BuildDerivationMap();

        // add start
        for (const cd of srcList) {
            queue.push(cd);
        }

        while (queue.length > 0) {
            const head = queue.shift();
            if (!head) {
                throw new Error("BUG，不应为空");
            }
            if (!box.addItem(head)) {
                continue;
            }

            // 放入待求队列
            const token = head.facedToken;
            if (token?.IsNonTerminal) { // 非终结符
                const nmap = this.cachedDerivationMap.get(token);
                if (!nmap) {
                    throw new Error("BUG，输入的语法 G 定义错误");
                }
                for (let nitem of nmap.values()) {
                    queue.push(new FamilyItemsLR0(nitem, 0));
                }
            }
        }

        return box;
    }

    cachedDerivationMap: Map<GrammarToken, Set<Derivation>> | null = null;

    /**
     * 重新计算语法相关信息
     */
    ReclaculateInfo(): ContainerMarkableBox<FamilyItemsSetLR0, GrammarToken> {
        this.cachedDerivationMap = this.g.BuildDerivationMap();
        // 计算项目集规范组
        // 第一项 start d list
        const theFirstItemSet = this.ExtendSetFrom(
            [...this.cachedDerivationMap.get(this.g.s) ?? []]
                .map(item => new FamilyItemsLR0(item, 0))
        );

        // map box
        const theMapBox = new ContainerMarkableBox<FamilyItemsSetLR0, GrammarToken>(
            FamilyItemsSetLR0.equal,
            (a, b) => a === b,
            theFirstItemSet,
        );

        // dui 
        const candicateList: FamilyItemsSetLR0[] = [theFirstItemSet];

        while (candicateList.length > 0) {
            const candicate = candicateList.shift() ?? theFirstItemSet;

            // next...
            for (let ifToken of [...this.g.vt, ...this.g.vn]) {

                // 
                const list: FamilyItemsLR0[] = [];
                for (let item of candicate.container) {
                    if (item.isShift() && item.facedToken == ifToken) { // 可以向后移入
                        list.push(new FamilyItemsLR0(item.dervation, item.pos + 1));
                    }
                }
                if (list.length > 0) {
                    const theBuiledSet = this.ExtendSetFrom(list);
                    const added = theMapBox.addNodeByEdge(candicate, ifToken, theBuiledSet);
                    if (added) {
                        candicateList.push(theBuiledSet);
                    }
                }
            }

            // ngg
        }

        return theMapBox;
    }

    static FromGrama(g: Grammar): FamilyItemsTableLR0 {
        var f = new FamilyItemsTableLR0(g);
        f.ReclaculateInfo();
        return f;
    }
}



/**
 * 计算 项目集规范族 LR(0)
 */
function ClacFamilyItemsLR0(g: Grammar): FamilyItemsTableLR0 {
    return FamilyItemsTableLR0.FromGrama(g);
}